package dp;

import java.util.Arrays;

/**
 * 198. 打家劫舍
 * 创建时间：2024-03-25 21:10
 * 地址：https://leetcode.cn/problems/house-robber/description/
 */
public class 打家劫舍_198 {
    /**
     * 从数组的第一个或者最后一个开始分析，这样受到的约束比较小
     * 因为不能连续偷，所以需要间隔：
     * dfs(i) = max(dfs(i - 1), dfs(i - 2) + nums[i])
     *
     */
    public int rob(int[] nums) {
        int n = nums.length;
        this.nums = nums;
        memo = new int[n];
        Arrays.fill(memo, -1);
        return dfs(n - 1);
    }

    private int[] nums, memo;
    public int dfs(int i) {
        if (i < 0) {
            return 0;
        }
        if (memo[i] > -1) {
            return memo[i];
        }
        int res = Math.max(dfs(i - 1), dfs(i - 2) + nums[i]);
        memo[i] = res;
        return res;
    }

    public static void main(String[] args) {
        打家劫舍_198 a = new 打家劫舍_198();
        System.out.println(a.rob(new int[]{1, 2, 3, 1}));
    }
}
